package com.ljy.my_study.lintcode.二分查找;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author James
 * @date 2018年9月21日
 */
public class TestMain {
	// 描述
	// 给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。
	//
	// 您在真实的面试中是否遇到过这个题？
	// 样例
	// 在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2。
	//
	// 挑战
	// 如果数组中的整数个数超过了2^32，你的算法是否会出错？

	public static void main(String[] args) {
		 int[] nums= {1,4,4,5,7,7,8,9,9,10};
//		 int[] nums= {3,4,5,8,8,8,8,10,13,14};
//		 int[] nums= {4,5,9,9,12,13,14,15,15,18};
		int[] nums1 = { 1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8,
				9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14,
				14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17,
				18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20 };
		TestMain testMain = new TestMain();
//		System.out.println(testMain.binarySearch(nums, 10));
		System.out.println(testMain.binarySerach(nums, 1));
		System.out.println(Arrays.binarySearch(nums, 4));
	}

	public int binarySerach(int[] array, int key) {
	    int left = 0;
	    int right = array.length - 1;
	    int min=-1;
	    while (left <= right) {
	        int mid = (left + right) / 2;
	        if (array[mid] == key) {
	        	if(min!=-1)min=Math.min(min, mid);
	        	else min=mid;
	        	if((min-1)>=0&&array[min-1]==key) {
	        		min=min-1;
	        		continue;
	        	}
	            return min;
	        }
	        else if (array[mid] < key) left = mid + 1;
	        else right = mid - 1;
	    }
	    return -1;
	}
	
	public int binarySearch(int[] nums, int target) {
		if (nums == null || nums.length == 0) {
			return -1;
		}
		return search(nums, 0, nums.length, target, -1);
	}
	private int search(int[] nums, int startIndex, int endIndex, int target, int minTargetIndex) {
		if(endIndex-startIndex<=30) {
			for(int i=startIndex;i<endIndex;i++) {
				if(nums[i]==target) {
					if(minTargetIndex!=-1) return Math.min(minTargetIndex, i);
					else return i;
				}
			}
			return minTargetIndex;
		}
		int minTargetIndex1 = -1;
		int minTargetIndex2 = -1;
		int midIndex = startIndex+(endIndex - startIndex) / 2;
		if (nums[midIndex] >= target) {
			if (nums[midIndex] == target) {
				minTargetIndex = midIndex;
			}
			minTargetIndex1 = search(nums, startIndex, midIndex, target, minTargetIndex);
		} else {
			minTargetIndex2 = search(nums, midIndex, endIndex, target, minTargetIndex);
		}
		if (minTargetIndex1 != -1 && minTargetIndex != -1) {
			minTargetIndex = Math.min(minTargetIndex, minTargetIndex1);
		} else if (minTargetIndex1 != -1) {
			minTargetIndex = minTargetIndex1;
		}
		if (minTargetIndex2 != -1 && minTargetIndex != -1) {
			minTargetIndex = Math.min(minTargetIndex, minTargetIndex2);
		} else if (minTargetIndex2 != -1) {
			minTargetIndex = minTargetIndex2;
		}
		return minTargetIndex;
	}

}
